class Solution {
public:
    int ret = 0;
    void mergeSort(vector<int>& nums,vector<int>& temp,int l,int r){
        if(l >= r) return;
        int mid = l + (r - l) / 2;
        mergeSort(nums,temp,l,mid);
        mergeSort(nums,temp,mid+1,r);
        
        int i = l;
        int j = mid + 1;
        int index = l;
 
        while(i <= mid && j <= r){
            if(nums[j] < nums[i]){
                temp[index++] = nums[j++];
            }else{
                temp[index] = nums[i];
                ret += index - i;
                index++;
                i++;
            }
        }
        while(i <= mid){
            temp[index++] = nums[i++];
            ret += index - i;
        }
        while(j <= r){
            temp[index++] = nums[j++];
        }
        
        index = l;
        for(i = l;i <= r;i++){
            nums[i] = temp[index++];
        }
    }
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        mergeSort(nums,tmp,0,nums.size() - 1);
        return ret;
    }
};
